#include "main/utils.h"
using namespace std;

int dfs(const vector<vector<int>>& matrix,
        vector<vector<int>>& length,
        int i,
        int j) {
  if (length[i][j])
    return length[i][j];

  vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  int max_length = 1;
  for (auto dir : dirs) {
    int next_i = i + dir[0];
    int next_j = j + dir[1];
    if (next_i >= 0 && next_i < matrix.size() &&
        next_j >= 0 && next_j < matrix[0].size() &&
        matrix[next_i][next_j] > matrix[i][j]) {
      int tmp_length = dfs(matrix, length, next_i, next_j) + 1;
      if (tmp_length > max_length) {
        max_length = tmp_length;
      }
    }
  }
  length[i][j] = max_length;
  return max_length;
}

int longestLength(const vector<vector<int>>& matrix) {
  int row = matrix.size();
  int col = matrix[0].size();
  vector<vector<int>> length;
  length.resize(row);
  for (int i = 0; i < row; ++i) {
    length[i].resize(col, 0);
  }

  int longest_length = 0;
  for (int i = 0; i < row; ++i) {
    for (int j = 0; j < col; ++j) {
      int cur_length = dfs(matrix, length, i, j);
      if (cur_length > longest_length) {
        longest_length = cur_length;
      }
    }
  }
  return longest_length;
}

int main() {
  vector<vector<int>> matrix = {{3, 4, 5}, {3, 2, 8}, {2, 2, 1}};
  cout << longestLength(matrix) << endl;

  return 0;
}
